const getHeight = (len: number) => {
  let height = 1;
  let num = 1;
  let ret = 0;
  let genArrForLen: number[] = [];
  let fun = (): [number, number, number[]] => {
    ret += num;
    genArrForLen.push(num);
    if (num >= len) {
      return [height, ret, genArrForLen];
    }

    height++;
    len -= num;
    num *= 2;
    return fun();
  };
  return fun();
};

let template: Array<string | number> = [];
let rootCopy: Array<null | number> = [];

const genArr = (index: number, floor: number): Array<string> => {
  let arr = Array.from({ length: floor }).fill("");
  if (!template.length) template = arr.slice() as Array<string | number>;
  if (index === 1) {
    let value = rootCopy.shift() as number;
    arr[Math.floor(floor / 2)] = value;
    template[Math.floor(floor / 2)] = value;
  } else {
    let left = 0;
    let right = 0;

    for (let i = 1; i <= index; i++) {
      left = right ? right + 1 : right;
      right =
        template.indexOf(1, left) == -1
          ? arr.length - 1
          : template.indexOf(1, left);
      let id = left === right ? left : Math.floor((right - left) / 2) + left;
      arr[id] = rootCopy.length ? rootCopy.shift() || "" : "";
      template[id] = 1;
    }
  }
  return arr as Array<string>;
};

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

const printTree = (root: Array<null | number>): Array<Array<string>> => {
  console.log("输入", root);
  rootCopy = root.slice();
  let len = root.length;
  let [height, floor, genArrForLen] = getHeight(len);
  let arr: Array<undefined> = [];
  arr.length = height;
  let newArr: Array<Array<string>> = [];
  for (let index = 0; index < arr.length; index++) {
    newArr.push(genArr(genArrForLen.shift() || 0, floor));
  }
  return newArr;
};

console.log(
  printTree([
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1, 1, 11, 1, 11, 1,
    11, 1, 1, 11, 1, 1, 11, 1, 1, 11, 1, 1, 11, 1, 1, 1, 11, 1, 1, 1, 1, 11, 1,
    1, 1, 11,
  ])
);
